#include<stdio.h>
#include<stdlib.h>
#include"Queue.h"
typedef char BTDataType;
typedef struct BinaryTreeNode
{
	BTDataType _data;
	struct BinaryTreeNode* _left;
	struct BinaryTreeNode* _right;
}BTNode;

BTNode* BuyBinaryTree(BTDataType x)//创建一个树的节点
{
	BTNode* BT = (BTNode*)malloc(sizeof(BTNode));
	if (BT == NULL)
	{
		printf("申请节点失败\n");
		exit(-1);
	}
	BT->_data = x;
	BT->_left = NULL;
	BT->_right = NULL;
	return BT;
}

void PreOrder(BTNode* root)//前序遍历
{
	if (root == NULL)
	{
		printf("NULL ");
		return;
	}
	printf("%c ", root->_data);
	PreOrder(root->_left);
	PreOrder(root->_right);
}
void InOrder(BTNode* root)//中序遍历
{
	if (root == NULL)
	{
		printf("NULL ");
		return;
	}
	InOrder(root->_left);
	printf("%c ", root->_data);
	InOrder(root->_right);
}
void PostOrder(BTNode* root)//后序遍历
{
	if (root == NULL)
	{
		printf("NULL ");
		return;
	}
	PostOrder(root->_left);
	PostOrder(root->_right);
	printf("%c ", root->_data);
}
void BinaryTreeLevelOrder(BTNode* root)//层序遍历
{
	Queue q;
	QueueInit(&q);
	if (root == NULL)
		return ;
	QueuePush(&q, root);
	while (!QueueEmpty(&q))
	{
		BTNode* front= QueueFront(&q);
		QueuePop(&q);
		printf("%c", front->_data);
		if (front->_left)
		{
			QueuePush(&q, front->_left);
		}

		if (front->_right)
		{
			QueuePush(&q, front->_right);
		}
	}
	QueueDestroy(&q);
	printf("\n");
}

int BinaryTreeComplete(BTNode* root)//判断是否为完全二叉树，是则返回1，否则返回0，
{
	//根据完全二叉树的性质特点，进行层序遍历遇到NULL跳出循环，若接下来遍历中遇到的全是NULL，则是完全二叉树
	Queue q;
	QueueInit(&q);
	if (root == NULL)
		return 0;
	QueuePush(&q, root);
	while (!QueueEmpty(&q))
	{
		BTNode* front = QueueFront(&q);
		QueuePop(&q);
		if (front == NULL)//层序遍历，遇到第一个NULL跳出。
		{
			break;
		}
		QueuePush(&q, front->_left);
		QueuePush(&q, front->_right);
	}
	while (!QueueEmpty(&q))//在后面序列中继续判断是否有非空
	{
		BTNode* front = QueueFront(&q);
		QueuePop(&q);
		if (front)
		{
			QueueDestroy(&q);//销毁
			return 0;
		}
	}
	QueueDestroy(&q);
	return 1;
}

int SizeBinaryTree(BTNode* root)//求树的大小，即节点的个数
{
	if (root == NULL)
		return 0;
	else
		return 1 + SizeBinaryTree(root->_left) + SizeBinaryTree(root->_right);
}
int SizeLeafTree(BTNode* root)//求树的叶子的个数
{
	if (root == NULL)
		return 0;
	else if (root->_left == NULL && root->_right == NULL)
		return 1;
	else
		return SizeLeafTree(root->_left) + SizeLeafTree(root->_right);
}
int MaxDepthTree(BTNode* root)//求树的深度
{
	
	if (root == NULL)
	{
		return 0;
	}
	else
	{
		int Ldep = MaxDepthTree(root->_left);
		int Rdep = MaxDepthTree(root->_right);
		return 1 + ((Ldep >= Rdep) ? Ldep : Rdep);
	}	
}
int BinaryTreeLevelKSize(BTNode* root,int k)//二叉树第K层节点的个数
{
	if (root == NULL)
		return 0;
	if (k == 1)
		return 1;
	else
		return BinaryTreeLevelKSize(root->_left, k - 1) + BinaryTreeLevelKSize(root->_right, k - 1);
}
BTNode* BinaryTreeFind(BTNode* root, BTDataType x)//二叉树查找值为X的节点，并能返回相对应的节点
{
	if (root == NULL)
	{
		return NULL;
	}
	if (root->_data == x)
	{
		return root;
	}
	BTNode* node = BinaryTreeFind(root->_left, x);//在左子树找，需要记录当前节点，对应则返回
	if (node)
		return node;
	node = BinaryTreeFind(root->_right, x);//在右子树找
	if (node)
		return node;
	return NULL;//找不到
}
void BinaryTreeDestroy(BTNode* root)//销毁二叉树，后序遍历销毁，不然先销毁头部可能会找不到子树
{
	if (root == NULL)
		return;
	BinaryTreeDestroy(root->_left);
	BinaryTreeDestroy(root->_right);
	free(root);
}
BTNode* CreatBinaryTree()//创建树
{
	BTNode* A = BuyBinaryTree('A');
	BTNode* B = BuyBinaryTree('B');
	BTNode* C = BuyBinaryTree('C');
	BTNode* D = BuyBinaryTree('D');
	BTNode* E = BuyBinaryTree('E');
	BTNode* F = BuyBinaryTree('F');
	A->_left = B;
	A->_right = C;
	B->_left = D;
	B->_right = E;
	C->_right = F;
	return A;
}
int main()
{
	BTNode* root = CreatBinaryTree();
	PreOrder(root);
	printf("\n");
	InOrder(root);
	printf("\n");
	PostOrder(root);
	printf("\n");
	int Tsz = SizeBinaryTree(root);
	printf("BinaryTree:%d\n", Tsz);
	int Lsz = SizeLeafTree(root);
	printf("LeafTree:%d\n", Lsz);
	int depth = MaxDepthTree(root);
	printf("DepthTree:%d\n", depth);
	int LevelK = BinaryTreeLevelKSize(root, 3);
	printf("BinaryTreeLevelKSize:%d\n", LevelK);
	BinaryTreeLevelOrder(root);
	int Btc=BinaryTreeComplete(root);
	printf("BinaryTreeComplete:%d\n", Btc);
	return 0;
}
